package Graph;

import java.util.LinkedList;
import java.util.List;

public class Dfs {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        v1.edges = List.of(new Edge(v2, 7),
                new Edge(v6, 14),
                new Edge(v3, 9)
        );
        v2.edges = List.of(new Edge(v4, 15)
        );

        v3.edges = List.of(new Edge(v6, 2),
                new Edge(v4, 11)
        );
        v6.edges = List.of(new Edge(v5, 9)
        );
        v4.edges = List.of(new Edge(v5, 6)
        );
        v5.edges = List.of();
        //深度优先
//        dfs(v1);
        System.out.println("====");
        bfs(v1);
    }

    public static void dfs(Vertex v) {
        v.visited = true;
        System.out.println(v.name);
        for (Edge edge : v.edges) {
            if (!edge.linked.visited) {
                dfs(edge.linked);
            }
        }
    }

    public static void bfs(Vertex v) {
        LinkedList<Vertex> queue = new LinkedList<>();
        queue.offer(v);
        v.visited = true;
        while (!queue.isEmpty()) {
            Vertex poll = queue.poll();
            System.out.println(poll.name);
            for (Edge edge : poll.edges) {
                if (!edge.linked.visited) {
                    edge.linked.visited = true;
                    queue.offer(edge.linked);
                }
            }
        }


    }


}
